#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <functional>
#include "tiempo.h"

using namespace std;

typedef int Paquete;
typedef int Camion;

void leerStdin();
void repartir(vector<Paquete> &paquetes, vector<Camion> &camiones, int pesoMaxCamion, int iter);
void imprimir_tiempos_ejecucion(unsigned long long int cant_ciclos, int cant_elem, const char* archivoOut);

int main(int argc, char *argv[]) {
	leerStdin();
	printf("Fin de tests\n");
	return 0;
}

void leerStdin() {
	bool pesoMaxCamionFlag(true);

	int cantIter;
	cin >> cantIter;

	while(1) {
		/* Leer instancia */

		int pesoMaxCamion(0), cantPaquetes(0), pesoPaquete(0);

		if(!(cin >> pesoMaxCamion)) {
			break;
		}

		cin >> cantPaquetes;

		vector<Paquete> paquetes;
		vector<Camion> camiones;

		for(int i = 0; i < cantPaquetes; i++) {
			cin >> pesoPaquete;
			paquetes.push_back(pesoPaquete);
		}

		/* Resolver */
		repartir(paquetes, camiones, pesoMaxCamion, cantIter);
	}
}

void repartir(vector<Paquete> &paquetes, vector<Camion> &camiones, int pesoMaxCamion, int iter) {
	unsigned long long int start, end, res;
	res = 0;
	const char* archivoOut = "res_performance.txt";

	for (int j=0; j < iter; j++) {
		MEDIR_TIEMPO_START(start);

		camiones.push_back(0);
		make_heap(camiones.begin(), camiones.end(), greater<Camion>());
		Camion actual;

		for(int i=0; i < paquetes.size() ; i++) {
			if(pesoMaxCamion >= camiones.front() + paquetes[i]) {
				camiones.front() += paquetes[i];
				actual = camiones.front();
				pop_heap(camiones.begin(), camiones.end(), greater<Camion>());
				camiones.pop_back();
			} else {
				actual = paquetes[i];
			}
			camiones.push_back(actual);
			push_heap(camiones.begin(), camiones.end(), greater<Camion>());
		}

		MEDIR_TIEMPO_STOP(end);
		res = res + (end-start);
	}

	res = res / iter;
	imprimir_tiempos_ejecucion(res, paquetes.size(), archivoOut);
}

void imprimir_tiempos_ejecucion(unsigned long long int cant_ciclos, int cant_elem, const char* archivoOut) {
	FILE* archivo = fopen(archivoOut, "a" );
	
	fprintf(archivo, "%i\t", cant_elem);
	fprintf(archivo, "%i\n", (unsigned int)cant_ciclos);	
	 
	fclose(archivo);
}